#ifndef MSC_BITMAP_H
#define MSC_BITMAP_H

#include "mem_base.h"

#define MS_BITMAP_ALLOCSIZE(n)  ((n)/8+1)

typedef struct ms_bitmap_s {
    ms_alloc_t* ac; //内存管理工具
    size_t size;   //最大值
    unsigned char* first;    //首地址
}ms_bitmap_t, *ms_bitmap;

CPUBLIC ms_bitmap ms_bitmap_create(ms_alloc_t* ac, size_t size) {
    if (!ac) {
        ac = ms_global_alloc();
    }
    ms_bitmap b = (ms_bitmap)ms_allocate(ac, sizeof(ms_bitmap_t));
    if (b) {
        b->ac = ac;
        b->size = size;
        if (b->size) {
            b->first = (unsigned char*)ac->allocate(ac, MS_BITMAP_ALLOCSIZE(b->size));
            if (!b->first) {
                ms_deallocate(ac, b);
                b = NULL;
            }
        }
        else
            b->first = NULL;
    }
    return b;
}

CPUBLIC void ms_bitmap_destory(ms_bitmap b) {
#ifdef _IF_NULL_
    if (b) {
#endif
    if (b->first) {
        ms_deallocate(b->ac, b->first);
    }
    ms_deallocate(b->ac, b);
#ifdef _IF_NULL_
    }
#endif
}

CPUBLIC void ms_bitmap_clear(ms_bitmap b) {
    if (b && b->size) {
        memset(b->first, 0, MS_BITMAP_ALLOCSIZE(b->size));
    }
}

CPUBLIC bool ms_bitmap_empty(ms_bitmap b) {
    return (NULL == b) || (0 == b->size);
}

CPUBLIC size_t ms_bitmap_size(ms_bitmap b) {
#ifdef _IF_NULL_
    if (b) {
#endif
    return b->size;
#ifdef _IF_NULL_
    }
    return 0;
#endif
}

static inline void ms_bitmap_reallocate(ms_bitmap b, size_t size) {
    if (b->first) {
        void* newp = NULL;
        if (b->ac->reallocate) {
            newp = ms_reallocate(b->ac, b->first, MS_BITMAP_ALLOCSIZE(size));
        }
        else {
            newp = ms_allocate(b->ac, MS_BITMAP_ALLOCSIZE(size));
            if (newp) {
                memcpy(newp, b->first, b->size);
                ms_deallocate(b->ac,b->first);
                b->first = NULL;
            }
        }
        if (newp) {
            b->size = size;
            b->first = (unsigned char*)newp;
        }
    }
    else {
        b->first = (unsigned char*)ms_allocate(b->ac, MS_BITMAP_ALLOCSIZE(size));
        if (b->first) {
            b->size = size;
        }
    }
}

CPUBLIC size_t ms_bitmap_resize(ms_bitmap b, size_t size) {
#ifdef _IF_NULL_
    if (b) {
#endif
    if (MS_BITMAP_ALLOCSIZE(b->size) == MS_BITMAP_ALLOCSIZE(size)) {
        b->size = size;
    }
    else {
        ms_bitmap_reallocate(b, size);
    }
    return b->size;
#ifdef _IF_NULL_
    }
    return 0;
#endif
}

CPUBLIC bool ms_bitmap_set(ms_bitmap b, size_t i) {
#ifdef _IF_NULL_
    if (b) {
#endif
    if (i > b->size) {
        if (MS_BITMAP_ALLOCSIZE(i) > MS_BITMAP_ALLOCSIZE(b->size)) {
            if (ms_bitmap_resize(b, i) != i) return false;
        }
        b->size = i;
    }
    size_t pos = i/8;
    unsigned char uc = 1 << (i%8);
    b->first[pos] |= uc;
    return true;
#ifdef _IF_NULL_
    }
    return false;
#endif
}

CPUBLIC void ms_bitmap_remove(ms_bitmap b, size_t i) {
#ifdef _IF_NULL_
    if (b) {
#endif
    if (i <= b->size) {
        size_t pos = i/8;
        unsigned char uc = 1 << (i%8);
        b->first[pos] &= 255 - uc;
    }
#ifdef _IF_NULL_
    }
#endif
}

CPUBLIC bool ms_bitmap_get(ms_bitmap b, size_t i) {
#ifdef _IF_NULL_
    if (b) {
#endif
    if (i <= b->size) {
        size_t pos = i/8;
        unsigned char uc = 1 << (i%8);
        return (b->first[pos] & uc) == uc;
    }
#ifdef _IF_NULL_
    }
#endif
    return false;
}

//取一个没有被占用的值
CPUBLIC size_t ms_bitmap_make(ms_bitmap b) {
    size_t id = 0;
#ifdef _IF_NULL_
    if (b) {
#endif
    size_t pos=1;
    for (; pos<MS_BITMAP_ALLOCSIZE(b->size); ++pos) {
        if (b->first[pos] != 255) {
            for (unsigned char c = 0; c < 8; ++c) {
                if (!(b->first[pos] & (1 << c))) {
                    id = pos * 8 + c;
                    b->first[pos] |= 1 << c;
                    if (id > b->size)
                        b->size = id;
                    break;
                }
            }
            break;
        }
    }
    if (0 == id) {
        if (b->size < 8)
            id = 8; //最小为8
        else
            id = b->size + 1;
        if (!ms_bitmap_set(b, id)) {
            id = 0;
        }
    }
#ifdef _IF_NULL_
    }
#endif
    return id;
}
#endif // MSC_BITMAP_H
